package leetcode.N1_N100;

/**
 * @author xiwai [hww282306@alibaba-inc.com]
 * @version 1.0
 * @date 2020/10/20 4:38 下午
 */
public class N60 {

    public static void main(String[] args) {
        System.out.println(getPermutation(3, 3));
    }

    public static String getPermutation(int n, int k) {
        int[] nums = new int[n];
        for (int i = 1; i <= n; i++) {
            nums[i - 1] = i;
        }
        return getValue(nums, k);
    }

    private static String getValue(int[] nums, int k) {
        int length = nums.length;
        if (length == 0) {
            return "";
        }
        int all = 1;
        for (int i = 1; i <= length; i++) {
            all *= i;
        }
        if (k == all || k == 0) {
            return max(nums);
        }
        if (k == 1) {
            return min(nums);
        }
        int i = all / length;
        int index = k / i;
        k = k % i;
        int val = nums[index];
        int[] newnums = new int[length - 1];
        for (int i1 = 0; i1 < nums.length; i1++) {
            if (i1 < index) {
                newnums[i1] = nums[i1];
            } else if (i1 > index) {
                newnums[i1 - 1] = nums[i1];
            }
        }
        String value = getValue(newnums, k);
        return val + value;
    }

    private static String max(int[] nums) {
        String val = "";
        for (int i = nums.length - 1; i >= 0; i--) {
            val += nums[i];
        }
        return val;
    }

    private static String min(int[] nums) {
        String val = "";
        for (int i = 0; i < nums.length; i++) {
            val += nums[i];
        }
        return val;
    }
}
